package com.easy.leetcode.array;

import java.util.Arrays;

/**
 * @ClassName NextPermutation31
 * @Description 31. 下一个排列
 * @Author zheng
 * @Date 2021/9/8 16:40
 * @Version 1.0
 **/
public class NextPermutation31 {
    public void nextPermutation(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return;
        }
        //从后向前，如果是递增的，那么这些位置上的数是最大值，找不到比这个更大的了
        //只能找一个非递增的索引
        //从后向前，从当前数组中找一个非递增的索引
        int i = length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        //从后向前，到i 的位置，都是递增的
        //找一个比i位置上大的数的索引
        //交换
        if (i >= 0) {
            int j = length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        //翻转i+1到末尾
        reverse(nums, i + 1, length - 1);
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public void reverse(int[] arr, int i, int j) {
        while (i < j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
}
